The present invention relates to an image processing method and apparatus and, more particularly, to an image processing method and apparatus for extracting an outline loop of a binary image input in a raster scan order.
When an outline font is to be formed from a binary dot pattern, an outline loop of a binary image character pattern is extracted, and the extracted outline loop is stored in a vector information format, thereby forming the outline font of the character. In order to extract an outline loop from such a binary image, a trace start point for outline loop trace in a binary image is initially found. When the trace start point is found, the outline of the image is traced in turn from the trace start point, and the trace is continued while adding trace end marks to traced outline points. When the trace makes a round, a one outline point array (outline loop) is obtained. Upon repetition of such a procedure, all outline loops in the image can be extracted.
Upon execution of outline trace, since there are eight pixels around a certain pixel, a total of eight trace direction s are present.
FIG. 2 shows an eight-coupling outline trace procedure. Referring to FIG. 2, reference numeral 201 denotes a binary image pattern including an inner blank portion 202. A case will be exemplified below wherein the outline loop of the pattern 201 is extracted. Note that one square in FIG. 2 indicates one dot (pixel).
(1) The binary image pattern 201 is raster-scanned from a reference point (0, 0) of a screen.
(2) When the raster-scan operation meets a point where a pixel without a trace end mark (e.g., a dot 203), the point is defined as P.sub.0, and outline trace of the dot pattern is started. If no point P.sub.0 is present after the entire screen is scanned, the procedure ends.
(3) A search operation is started in eight neighboring pixel directions neighboring the start point P.sub.0 in the order shown in FIG. 3. Then, a point (a dot 204 in FIG. 2), where a first detected black pixel neighboring a white pixel is present, is defined as the next outline point P.sub.1. In this case, when no neighboring points are present, the point is defined as an isolated point, and the control returns to the procedure (2).
(4) In this manner, a point Pi is marked, and the next outline point P.sub.i+1 is extracted from neighboring pixels in eight directions neighboring the point P.sub.i, as shown in FIG. 4. From a previously marked point 401, whether or not a dot is present is searched counterclockwise about the point P.sub.i (dot 204), and a point where a first detected pixel is present is defined as the next outline point P.sub.i+1.
(5) Thereafter, the procedure (4) is repeated to sequentially obtain outline points. When P.sub.n+1 =P.sub.1, and P.sub.n =P.sub.0, the points P.sub.0, P.sub.1, . . . , P.sub.n-1 are defined as an outline point array of one region, and the control advances to a procedure (6).
(6) The control returns to the procedure (2) to obtain an outline point array of another image region.
Note that, in FIGS. 3 and 4, the central portion indicates a point of interest, the notation of .circleincircle. (401) indicates a previously marked point. Note that numerals in FIGS. 3 and 4 represent the search order of the presence/absence of a pixel (dot).
However, in the above-mentioned procedures, since the trace operation is performed along an outline loop after the outline trace start point is determined, extraction processing of an outline loop must be started after the entire image is stored on a memory. For this reason, the required memory capacity becomes large, resulting in an increase in cost, a long processing time, and the like.
In order to reduce the memory capacity, a method of extracting an outline point based on the states of a pixel of interest and its neighboring pixels by fetching an image in the raster-scan order has been proposed previously. This method has a connection information table for holding connection states of outline loops in units of pixels, and after outlines are extracted for all pixels in the image, the connection information table is scanned again to obtain a total number of loops of outline vectors, the number of outline points constituting each loop, the coordinate values of outline points constituting each loop, and the like.
However, with this method, after outline (coarse outline) vectors are extracted for all pixels in an image, the connection information table is scanned again to obtain a total number of loops of outline vectors, the number of outline points constituting each loop, the coordinate values of outline points constituting each loop, and the like. For this reason, the capacity of the connection information table becomes undesirably large since it must hold all connection information of outline points in the image, resulting in a decrease in search speed of the table.